package leetcode.f1t100;

/**
 * log(n)查找旋转后的有序列表(3,4,0,1,2)
 * https://leetcode.com/problems/search-in-rotated-sorted-array/
 *
 * @Author lichongxiao
 * @Date 2022/10/9 10:13
 */
public class Q33_SearchInRotatedSortedArray {

    public int search2(int[] nums, int target) {
        int left = 0, right = nums.length-1, middle;
        while(left<=right){
            middle = (left+right)/2;
            if(nums[middle] == target){
                return middle;
            }
            if(nums[left] <= nums[middle]){
                if(nums[left] <= target && target < nums[middle]) {
                    right = middle -1;
                }else {
                    left = middle + 1;
                }
            }else {
                if(nums[middle] < target && target <= nums[right]) {
                    left = middle + 1;
                } else {
                    right = middle -1;
                }
            }
        }
        return -1;
    }

    public int search1(int[] nums, int target) {
        int start = findMinNum(nums);
        int index = binarySearch(nums, 0, start-1, target);
        if (index < 0) {
            index = binarySearch(nums, start, nums.length - 1, target);
        }
        return index;
    }

    private int findMinNum(int[] nums){
        int left = 0, middle = 0, right = nums.length - 1;
        while (left < right) {
            middle = (left + right) / 2;
            if (nums[middle] > nums[right]) {
                left = middle+1;
            } else if(nums[middle] < nums[right]){
                right = middle;
            }
        }
        return left;
    }

    private int binarySearch(int[] nums, int left, int right, int target){
        int middle = 0;
        while(left <= right){
            middle = (left + right) / 2;
            if(nums[middle] == target){
                return middle;
            } else if(nums[middle] < target) {
                left = middle+1;
            } else {
                right = middle-1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3,1,5};
//        System.out.println(new Q33_SearchInRotatedSortedArray().search(nums,4));
        System.out.println(new Q33_SearchInRotatedSortedArray().search1(nums,1));
    }
}
